package com.wlient.basic.Sort;

import java.util.Arrays;

public class Quick_Sort {
    public static void main(String[] args) {
        int[] arr=new int[]{4,2,8,0,5,7,1,3,9};
        System.out.println(Arrays.toString(QuickSort(arr,0,arr.length-1)));
    }

    public static int[] QuickSort(int[] arr,int start,int end){
        //起始
        int i=start;
        int j=end;
        //获取基准数
        int temp=arr[start];
        //i<j为循环条件
        if(i<j){
            while(i<j){
                //从右向左去找比基准数小的
                while(i<j&&arr[j]>=temp){
                    j--;
                }
                //判断相等，填坑
                if(i<j){
                    arr[i]=arr[j];
                    i++;
                }
                //从左向右去找比基准数大的
                while(i<j&&arr[i]<temp){
                    i++;
                }
                //判断相等，填坑
                if(i<j){
                    arr[j]=arr[i];
                    j--;
                }
            }
            //把基准数放到i=j的位置
            arr[i]=temp;
            //对左半边部分进行快排
            QuickSort(arr,start,i-1);
            //对右半边部分进行快排
            QuickSort(arr,i+1,end);
        }
        return arr;
    }
}